package class3;

/**
 * 使用链表实现双端队列
 */
public class Code05_DoubleQueue {
    public static void main(String[] args) {
        DoubleQueue<Integer> doubleQueue = new DoubleQueue<>();
        // 从头部差入数据
//        doubleQueue.addFirst(1);
//        doubleQueue.addFirst(2);
//        doubleQueue.addFirst(3);
//        doubleQueue.addFirst(4);
        // 头部出队
//        doubleQueue.removeFirst();
//        doubleQueue.removeFirst();
//        doubleQueue.removeFirst();
//        doubleQueue.removeFirst();
        // 从尾部插入
        doubleQueue.addLast(1);
        doubleQueue.addLast(2);
        doubleQueue.addLast(3);
        doubleQueue.addLast(4);
        // 尾部出队
        doubleQueue.removeLast();
        doubleQueue.removeLast();
        doubleQueue.removeLast();
        doubleQueue.removeLast();
        doubleQueue.removeLast();
        System.out.println(doubleQueue);
    }

    static class Node<V> {
        V val;
        Node<V> pre;
        Node<V> next;

        public Node(V val) {
            this.val = val;
        }
    }

    static class DoubleQueue<V> {

        public Node<V> head;
        public Node<V> tail;
        public int size;

        public DoubleQueue() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }


        public void addFirst(V v) {
            Node<V> cur = new Node<>(v);
            if (head == null) {
                head = tail = cur;
            } else {
                cur.next = head;
                head.pre = cur;
                head = cur;
            }
            size++;
        }

        public V removeFirst() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = head.val;
            if (head == tail) {
                head = tail = null;
            } else {
                head = head.next; // 头指针右移
                head.pre = null;
            }
            return ans;
        }

        // 队尾添加
        public void addLast(V v) {
            Node<V> cur = new Node<>(v);
            if (tail == null) {
                head = tail = cur;
            } else {
                tail.next = cur;
                cur.pre = tail;
                tail = cur;
            }
            size++;
        }

        // 尾部出队
        public V removeLast() {
            V ans = null;
            if (tail == null) {
                return ans;
            }
            ans = tail.val;
            size--;
            if (head == tail) {
                head = tail = null;
            }else{
                tail = tail.pre;
                tail.next = null;
            }

            return ans;
        }

        // 队尾出
    }

}
